package queue

import (
	"errors"
	"fmt"
	"strings"
)

// LoopQueue 循环队列
type LoopQueue[E any] struct {
	data        []E
	front, tail int //front 队首索引，tail 下一个队尾索引
	size        int
}

func MakeLoopQueue0[E any](capacity int) *LoopQueue[E] {
	return &LoopQueue[E]{
		//真实容量会多一个空间，用来区分：
		//队列为空，tail==front
		//队列满，（tail+1）% len(data)==front
		data: make([]E, capacity+1, capacity+1),
	}
}

func MakeLoopQueue[E any]() *LoopQueue[E] {
	return MakeLoopQueue0[E](10)
}

func (l *LoopQueue[E]) GetCap() int {
	return cap(l.data) - 1
}

func (l *LoopQueue[E]) GetSize() int {
	return l.size
}

func (l *LoopQueue[E]) GetFront() (E, error) {
	var zero E
	if l.IsEmpty() {
		return zero, errors.New("queue is empty")
	}
	return l.data[l.front], nil
}

func (l *LoopQueue[E]) DeEnqueue() (E, error) {
	var zero E
	if l.IsEmpty() {
		return zero, errors.New("cannot dequeue from an empty queue")
	}

	e := l.data[l.front]
	l.front = (l.front + 1) % cap(l.data) //真实容量
	l.size--
	//1/4缩容一半,缩容后的容量不能为0，否则无法扩容
	if l.GetSize() == l.GetCap()/4 && l.GetCap()/2 != 0 {
		l.resize(l.GetCap() / 2)
	}

	return e, nil
}

func (l *LoopQueue[E]) Enqueue(e E) error {
	// 队列满，2倍扩容
	//if l.size == l.GetCap() {
	//	l.resize(2 * l.GetCap())
	//}
	if (l.tail+1)%cap(l.data) == l.front {
		l.resize(2 * l.GetCap())
	}
	l.data[l.tail] = e
	l.tail = (l.tail + 1) % cap(l.data) //真实容量
	l.size++
	return nil
}

func (l *LoopQueue[E]) IsEmpty() bool {
	return l.front == l.tail
}

func (l *LoopQueue[E]) resize(capacity int) {
	newData := make([]E, capacity+1, capacity+1)
	for i := 0; i < l.size; i++ {
		//newData[i] = l.data[l.front]
		//l.front = (l.front + 1) % cap(l.data) //真实容量
		newData[i] = l.data[(i+l.front)%cap(l.data)]
	}
	l.data = newData
	l.front = 0
	l.tail = l.size
}

func (l LoopQueue[E]) String() string {
	var sb strings.Builder
	sb.WriteString(fmt.Sprintf("Queue: size = %d , capacity = %d\n", l.size, l.GetCap()))
	sb.WriteString("front [")
	//index := l.front
	//for i := 0; i < l.size; i++ {
	//	e := l.data[index]
	//	sb.WriteString(fmt.Sprintf("%+v", e))
	//	if i != l.size-1 {
	//		sb.WriteString(", ")
	//	}
	//	index = (index + 1) % cap(l.data) //真实容量
	//}
	for i := l.front; i != l.tail; i = (i + 1) % cap(l.data) {
		e := l.data[i]
		sb.WriteString(fmt.Sprintf("%+v", e))
		if (i+1)%cap(l.data) != l.tail {
			sb.WriteString(", ")
		}
	}
	sb.WriteString("] tail")
	return sb.String()
}
